package com.bang.study.day05.leetcode;



/**
 * @Auther: Bang
 * @Date: 2019/9/17 0017 10:42
 * @Description: 211. 添加与搜索单词 - 数据结构设计
 *  设计一个支持以下两种操作的数据结构：
 *
 * void addWord(word)
 * bool search(word)
 * search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
 *
 * 示例:
 *
 * addWord("bad")
 * addWord("dad")
 * addWord("mad")
 * search("pad") -> false
 * search("bad") -> true
 * search(".ad") -> true
 * search("b..") -> true
 * 说明:
 *
 * 你可以假设所有单词都是由小写字母 a-z 组成的。
 *
 */
public class WordDictionary_2 {
    class Node{
        private boolean isEnd;

        private Node[] links;

        public Node() {
            links = new Node[26];
        }

        public boolean contains(char ch) {
            return links[ch - 'a'] != null;
        }

        public void put(char ch, Node node) {
            links[ch -'a'] = node;
        }

        public Node get(char ch) {
            return links[ch -'a'];
        }

        public boolean isEnd() {
            return isEnd;
        }

        public void setEnd(boolean flag) {
            isEnd = flag;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary_2() {
        this.root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
           if (!curr.contains(c)){
               curr.put(c, new Node());
           }
            curr = curr.get(c);
        }
        curr.setEnd(true);
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return search(root, word, 0);
    }

    /**
     *
     * @param node
     * @param word
     * @param index
     * @return
     */
    private boolean search(Node node, String word, int index) {
        if (word.length() == index) {
            return node.isEnd;
        }
        char c = word.charAt(index);
        if (c == '.') {
            // 通配符
            Node[] links = node.links;
            for (int i = 0; i < links.length; i++) {
                Node link = links[i];
                if (null!=link){
                    if (search(link, word, index + 1)){
                        return true;
                    }
                }
            }
            // 循环走完 仍未匹配到 则返回false
            return false;
        } else {
            // 非通配符
            if (!node.contains(c)) {
                return false;
            } else {
                return search(node.get(c), word, index + 1);
            }
        }
    }

  
    public static void main(String[] args) {
        WordDictionary_2 wordDictionary = new WordDictionary_2();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println( wordDictionary.search("pad"));
        System.out.println( wordDictionary.search("bad"));
        System.out.println( wordDictionary.search(".ad"));
        System.out.println( wordDictionary.search("b.."));
        wordDictionary.search("pad");// false
        wordDictionary.search("bad");// true
        wordDictionary.search(".ad");// true
        wordDictionary.search("b..");// true

    }
}
